package lc;

public class Ex69 {
    class Solution {
        public int mySqrt(int x) {
            if (x == 0) return 0;
            double limit = (double)x / 2.0;
            double lo = 0, hi = limit, tmp;
            while (lo <= hi) {
                double mid = (hi - lo) / 2 + lo;
                tmp = mid * mid;
                if (Math.abs(tmp - (double)x) < 0.5) {
                    return (int)mid;
                } else if (tmp > x){
                    hi = mid + 0.5;
                } else {
                    lo = mid + 0.5;
                }
            }
            return 0;
        }
    } 
}
